#include <stdio.h>
#include <stdlib.h>

// 线索二叉树结点
typedef struct BTNode
{
    int data;
    struct BTNode *lchild, *rchild;
    int ltag, rtag; // 左右线索标志，tag == 0表示指针指向孩子，tag == 1表示指针是线索
} BTNode, *BTree;

// 辅助全局变量，用于查找p的前驱
BTNode *pre = NULL; // 指向当前访问结点的前驱

void visit(BTNode *q)
{
    if (q->lchild == NULL) // 左树为空，建立前驱线索
    {
        q->lchild = pre;
        q->ltag = 1;
    }
    if (pre != NULL && pre->rchild == NULL)
    {
        pre->rchild = q; // 建立前驱结点的后继线索
        pre->rtag = 1;
    }
    pre = q;
}

// 中序遍历
void InOrder(BTree &T)
{
    if (T != NULL)
    {
        InOrder(T->lchild); // 递归遍历左树
        visit(T);           // 访问根节点
        InOrder(T->rchild); // 递归遍历右树
    }
}

// 先序遍历
void PreOrder(BTree &T)
{
    if (T != NULL)
    {
        visit(T);
        if (T->ltag == 0)
        {
            PreOrder(T->lchild);
        }
        PreOrder(T->rchild);
    }
}

// 后续遍历
void PostOrder(BTree &T)
{
    if (T != NULL)
    {
        PreOrder(T->lchild);
        PreOrder(T->rchild);
        visit(T);
    }
}

// 中序线索化二叉树
void CreateInTree(BTree &T)
{
    pre = NULL;    // pre 初始为NULL
    if (T != NULL) // 非空二叉树才能线索化
    {
        InOrder(T); // 中序线索化二叉树
        if (pre->rchild == NULL)
        {
            pre->rtag = 1; // 处理遍历的最后一个结点
        }
    }
}

// 先序线索化二叉树
void CreatePreTree(BTree &T)
{
    pre = NULL;    // pre 初始为NULL
    if (T != NULL) // 非空二叉树才能线索化
    {
        PreOrder(T); // 中序线索化二叉树
        if (pre->rchild == NULL)
        {
            pre->rtag = 1; // 处理遍历的最后一个结点
        }
    }
}

// 后序线索化二叉树
void CreatePostTree(BTree &T)
{
    pre = NULL;    // pre 初始为NULL
    if (T != NULL) // 非空二叉树才能线索化
    {
        PostOrder(T); // 中序线索化二叉树
        if (pre->rchild == NULL)
        {
            pre->rtag = 1; // 处理遍历的最后一个结点
        }
    }
}

// 找到以p为根的子树中，第一个被中序遍历的结点
BTNode *FirstNode(BTNode *p)
{
    while (p->ltag == 0)
    {
        p = p->lchild;
    }
    return p;
}

// 在中序线索化二叉树中找到结点p的后继结点
BTNode *NextNode(BTNode *p)
{
    if (p->rtag == 0)
    {
        return FirstNode(p->rchild);
    }
    else
    {
        return p->rchild;
    }
}

// 对中序线索二叉树进行中序遍历
void Inorder(BTNode *T)
{
    for (BTNode *p = FirstNode(T); p != NULL; p = NextNode(p))
    {
        visit(p);
    }
}

// 找到以p为根的子树中，最后一个被中序遍历的结点
BTNode *LastNode(BTNode *p)
{
    while (p->rtag == 0)
    {
        p = p->rchild;
    }
    return p;
}

// 在中序线索二叉树中找到p的前驱结点
BTNode *PreNode(BTNode *p)
{
    if (p->ltag == 0)
    {
        return LastNode(p->lchild);
    }
    else
    {
        return p->lchild;
    }
}

// 对中序线索二叉树进行逆向中序遍历
void Preorder(BTNode *T)
{
    for (BTNode *p = LastNode(T); p != NULL; p = PreNode(p))
    {
        visit(p);
    }
}